import java.util.Arrays;
import java.util.Stack;

/**
 * Creat with IntelliJ IDEA
 * Description:
 * User:WZW
 * Date:2022-02-25
 * Time:20:21
 */
public class TestSort {

    public static void swap(int[] array, int a,int b){
        int tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }





    /**
     * 时间复杂度：O(n^2) 逆序的时候
     *          最好的情况时O(n)：对于直接插入排序，最好的情况就是数据有序的时候
     *          根据这个结论，推导出另一个结论：对于直接插入排序来说，数据越有序，越快
     * 空间复杂度：O(1)
     * 稳定性：稳定的
     * @param array
     */
    public static void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >= 0 ; j--) {
                if (array[j] > tmp){
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            //j回退到了 小于0的地方
            array[j+1] = tmp;
        }
    }


    /**
     * 希尔排序
     * 时间复杂度：O(n^1.3-O^1.5)
     * 空间复杂度：O(1)
     * 稳定性：不稳定的
     * 看在比较的过程当中，是否发生了跳跃性的交换
     * @param array
     * @param gap
     */
    public static void shell(int[] array, int gap){
        for (int i = gap; i < array.length ; i++) {
            int j = i-gap;
            int tmp = array[i];
            while(j >= 0){
                if(tmp < array[j]){
                    array[j+gap] = array[j];
                    j -= gap;
                }else {
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }

    public static void shellSort(int[] array){
        int gap = array.length;
        while (gap > 1){
            shell(array,gap);
            gap /= 2;
        }
        shell(array,1);
    }


    /**\
     * 选择排序
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array 待排序数组
     */
    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length-1; i++) {
            for (int j = i+1; j < array.length ; j++) {
                if(array[i]>array[j]){
                    swap(array, i, j);
                }
            }
        }
    }
    public static void selectSort1(int[] array) {
        for (int i = 0; i < array.length-1; i++) {
            int k = i;
            for (int j = i+1; j < array.length ; j++) {
                if(array[k]>array[j]){
                    k = j;
                }
            }
            if(k!=i){
                int tmp = array[i];
                array[i] = array[k];
                array[k] = tmp;
            }
        }
    }

    /**
     * 堆排序
     * 时间复杂度：O(n*logn)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array
     */
    public static void heapSort(int[] array){
        //1.建堆
        createHeap(array);
        int end = array.length-1;
        //2.交换然后调整
        while(end>0){
            swap(array,0,end);
            shiftDown(array,0,end);
            end--;
        }
    }

    public static void createHeap(int[] array){
        for (int parent = ((array.length)-1-1)/2; parent >= 0; parent--){
            shiftDown(array,parent,array.length);
        }
    }

    public static void shiftDown(int[] array,int parent, int len){
        int child = parent*2+1;
        while (child < len){
            if (child+1 < len && array[child]<array[child+1]){
                child++;
            }
            if (array[child] > array[parent]){
                swap(array,child,parent);
                parent = child;
                child = parent*2+1;
            }else {
                break;
            }
        }
    }

    public static void insertSort2(int[] array,int start ,int end){
        for (int i = 1; i <= end ; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >= 0 ; j--) {
                if (array[j] > tmp){
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j] = tmp;
        }
    }

    /**
     * 快速排序
     * @param array
     */
    public static void quickSort2(int[] array){
        quick(array,0,array.length-1);
    }

    private static void quick(int[] array, int left, int right){
        if (left >= right){
            return;
        }
        if (right-left+1 <= 4000){
            //使用直接插入排序
            insertSort2(array,left,right);
            return;
        }
        //三数取中
        int midValIndex = findMidValIndex(array,left,right);
        swap(array,left,midValIndex);
        //找基准
        int pivot = partition(array,left,right);//基准
        //递归
        quick(array,left,pivot-1);
        quick(array,pivot+1,right);
    }

    public static int findMidValIndex(int[] array, int start, int end){
        int mid = (end-start)>>>1;
        if (array[start]<array[end]){
            if (array[mid]<array[start]){
                return start;
            }else if (array[mid]>array[end]){
                return end;
            }else {
                return mid;
            }
        }else {
            if (array[mid]>array[start]){
                return start;
            }else if (array[mid]<array[end]){
                return end;
            }else{
                return mid;
            }
        }
    }

    private static int partition(int[] array, int start, int end){
        int tmp = array[start];
        while (start < end){
            while (start < end && array[end] >= tmp){
                end--;
            }
            array[start] = array[end];
            while (start < end && array[start] <= tmp){
                start++;
            }
            array[end] = array[start];
        }
        array[start] = tmp;
        return start;
    }

    /**
     * 快排的非递归实现
     * @param array
     */
    public static void quickSort1(int[] array){
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length-1;
        int pivot = partition(array,left,right);
        if (pivot > left+1){
            //左边有两个元素
            stack.push(left);
            stack.push(pivot-1);
        }
        if (pivot < right-1){
            //右边有两个元素
            stack.push(pivot+1);
            stack.push(right);
        }

        while (!stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();
            pivot = partition(array,left,right);
            if (pivot > left+1){
                stack.push(left);
                stack.push(pivot-1);
            }
            if (pivot < right-1){
                stack.push(pivot+1);
                stack.push(right);
            }
        }
    }

    /**
     * 归并排序
     * 时间复杂度：O(n*logn)
     * 空间复杂度：O(n)
     * 稳定性：稳定的
     * 如果 array[s1] <= array[s2] 不取等号，则是不稳定的
     *
     * 学过的排序中，只有3个是稳定的：
     * 冒泡 插入 归并
     *
     * @param array
     */
    public static void mergeSort(int[] array){
        mergerSortInternal(array,0,array.length-1);
    }

    private static void mergerSortInternal(int[] array, int low, int high){
        if (low>=high)return;
        int mid = (low+high)>>>1;
        //左边
        mergerSortInternal(array,low,mid);
        //右边
        mergerSortInternal(array,mid+1,high);
        //合并
        merge(array,low,mid,high);
    }

    private static void merge(int[] array, int left, int mid, int right){
        int[] tmp = new int[right-left+1];
        int k = 0;
        int s1 = left;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = right;
        while (s1 <= e1 && s2 <= e2){
            if (array[s1] <= array[s2]){
                tmp[k++] = array[s1++];
            }else {
                tmp[k++] = array[s2++];
            }
        }
        while (s1 <= e1){
            tmp[k++] = array[s1++];
        }
        while (s2 <= e2){
            tmp[k++] = array[s2++];
        }
        //将数据复制到原数组中
        for (int i = 0; i < k; i++) {
            array[i+left] = tmp[i];
        }
    }

    /**
     * 非递归实现归并排序
     * @param array
     */
    public static void mergeSort1(int[] array){
        int nums = 1;//每组数据的个数
        while (nums <= array.length){
            //数组每次都要进行遍历，并确定归并的区间
            for (int i = 0; i < array.length; i+= nums*2) {
                int left = i;
                int mid = left+nums-1;
                //防止越界
                if (mid >= array.length){
                    mid = array.length-1;
                }
                int right = mid+nums;
                //防止越界
                if (right >= array.length){
                    right = array.length-1;
                }
                //合并
                merge(array,left,mid,right);
            }
            nums *= 2;
        }
    }

    /**
     * 合并排序
     * @param array1
     * @param array2
     * @return
     */
    public static int[] mergeArray(int[] array1, int[] array2) {
        if (array1 == null) return array2;
        if (array2 == null) return array1;
        int[] ret = new int[array1.length + array2.length];
        int s1 = 0;
        int s2 = 0;
        int k = 0;
        while (s1 <= array1.length && s2 <= array2.length) {
            if (array1[s1] <= array2[s2]) {
                ret[k++] = array1[s1++];
            } else {
                ret[k++] = array2[s2++];
            }
        }
        while (s1 < array1.length) {
            ret[k++] = array1[s1++];
        }
        while (s2 < array2.length) {
            ret[k++] = array2[s2++];
        }
        return ret;
    }


    /**
     * 计数排序
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     * 稳定性：不稳定
     * 适用情况：有n个数，数据范围是0-n之间的
     * @param array
     */
    public static void countingSort(int[] array){
        int minVal = array[0];
        int maxVal = array[0];
        for (int i = 0; i < array.length; i++) {
            if (minVal > array[i]){
                minVal = array[i];
            }
            if (maxVal <= array[i]){
                maxVal = array[i];
            }
        }
        int[] count = new int[maxVal-minVal+1];
        for (int i = 0; i < array.length; i++) {
            count[array[i]-minVal]++;
        }
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            if (count[i] > 0){
                array[index++] = i+minVal;
                count[i]--;
            }
        }
    }

    public static void main(String[] args) {
        int[] a = {12,5,18,10,4,2};
        shellSort(a);
        System.out.println(Arrays.toString(a));
    }
}
